//TODO: LeetCode94. 二叉树的中序遍历

//* 非递归
class Solution {
public:
    vector<int> inorderTraversal(TreeNode* root) {
        vector<int> ret;
        stack<TreeNode*> stk;

        TreeNode* cur = root;
        while (cur || !stk.empty()) {
            //先将树的左路节点入栈
            while (cur) {
                stk.push(cur);
                cur = cur->left;
            }

            TreeNode* top = stk.top();
            ret.push_back(top->val); //节点出栈的顺序与中序遍历的顺序一致
            stk.pop();

            cur = top->right;
        }

        return ret;
    }
};